package day1.TraversalBinaryTree;

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;

/**
 * @author pacai
 * @version 1.0
 */
@SuppressWarnings("all")
public class QuickSort {
    public static void splitNum(int[] arr) {
        int lessEqualR = -1;
        int index = 0;
        int mostR = arr.length - 1;
        while (index < arr.length) {
            if (arr[index] < arr[mostR]) {
                swap(arr, ++lessEqualR, index++);
            } else {
                index++;
            }
        }
    }

    public static void splitNum1(int[] arr) {
        int N = arr.length;
        int lessR = -1;
        int moreL = N - 1;
        int index = 0;
        while (index < moreL) {
            if (arr[index] < arr[N - 1]) {
                swap(arr, ++lessR, index++);
            } else if (arr[index] > arr[N - 1]) {
                swap(arr, --moreL, index);//>区和index位置的数交换,但<区不用右y移,因为当前数还没判断
            } else {
                index++;//=时只需移动
            }
        }
        swap(arr, moreL, N - 1);
    }

    //快排-递归
    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;//无需排序的情况
        }
        process(arr, 0, arr.length - 1);
    }

    public static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;//要判断出递归的条件
        }
        int[] range = partition(arr, L, R);
        process(arr, L, range[0] - 1);
        process(arr, range[1] + 1, R);
    }


    public static int[] partition(int[] arr, int L, int R) {
        int lessR = L - 1;
        int index = L;
        int moreL = R;
        while (index < moreL) {
            if (arr[index] < arr[R]) {
                swap(arr, ++lessR, index++);
            } else if (arr[index] > arr[R]) {
                swap(arr, --moreL, index);
            } else {
                index++;
            }
        }
        swap(arr, moreL, R);
        return new int[]{lessR + 1, moreL};
    }


    public static void swap(int[] arr, int i, int j) {
        if (j != i) {
            arr[i] ^= arr[j];
            arr[j] ^= arr[i];
            arr[i] ^= arr[j];
        }
    }

    private static class Job {
        int L;
        int R;

        public Job(int L, int R) {
            this.L = L;
            this.R = R;
        }
    }

    //快排-非递归
    public static void quickSort2(int[] arr) {
        if(arr == null || arr.length < 2){
            return;
        }
        Stack<Job> stack = new Stack<>();
        stack.push(new Job(0, arr.length - 1));
        while (!stack.isEmpty()) {
            Job cur = stack.pop();
            int[] ranges = partition(arr, cur.L, cur.R);
            //todo 需要判断是否还可以继续完成任务
            if (ranges[0] > cur.L) { //判断是否有 < 区域
                stack.push(new Job(cur.L, ranges[0] - 1));
            }
            if (ranges[1] < cur.R) { //判断是否有 > 区域
                stack.push(new Job(ranges[1] + 1, cur.R));
            }
        }
    }



    //对数器
    public static int[] getRandomArray(int n, int k) {
        int range = n;
        int max = k;
        Random random = new Random();
        int[] arr = new int[random.nextInt(n)];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(range);
        }
        return arr;
    }

    public static void main(String[] args) {
        int times = 500000;
        int maxrange = 100;
        int maxvalue = 100;
        for (int i = 0; i < times; i++) {
            int[] arr = getRandomArray(maxrange, maxvalue);
            int[] arr1 = arr.clone();
            int[] arr2 = arr.clone();
            quickSort1(arr1);
            quickSort2(arr2);
            Arrays.sort(arr);
            if(! Arrays.equals(arr1, arr2) || !Arrays.equals(arr, arr1)){
                System.out.println(Arrays.toString(arr));
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                System.out.println("Oops");
                return;
            }
        }
        System.out.println("success");
    }
}
